//
//  CommonSolution.h
//  leetcode
//
//  Created by Ellie on 2021/1/26.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef CommonSolution_h
#define CommonSolution_h

#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class CommonSolution
{
public:
    int myatoi(string str);
    // 189. 旋转数组
    void reverse(vector<int>& nums, int K);
    void reverse(vector<int>& nums, int start, int end);
    
    // 67. 二进制求和
    string addBinary(string a, string b);
    
    // 原地数组方案，不使用额外空间的情况下解决该问题并在O(n)的复杂度下解决问题
    // 该类型的问题能直接使用hashmap解决，但是不满足不使用额外的空间复杂度
    // 最关键的地方需要看清题目的输入，确定输入的范围，确定当前输入确定了某种解决方案
    // 41. 缺失的第一个正数
    int firstMissingPositive(vector<int>& nums);
    // 442. 数组中重复的数据
    vector<int> findDuplicates(vector<int>& nums);
    // 448. 找到所有数组中消失的数字
    vector<int> findDisappearedNumbers(vector<int>& nums);
    // 287. 寻找重复数和offer 03题目类似，只是映射关系不同
    int findDuplicate(vector<int>& nums);
    // 剑指 Offer 03. 数组中重复的数字
    int findRepeatNumber(vector<int>& nums);
    
    //
    //
    //    滑动窗口系列问题
    //
    //
    // 76. 最小覆盖子串 HARD
    string minWindow(string s, string t);
    // 567. 字符串的排列
    // 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
    // 换句话说，第一个字符串的排列之一是第二个字符串的子串。
    // 由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。
    // 排列问题转换成计数问题
    bool checkInclusion(string s1, string s2);
    // 567. 使用76类似的思路框架
    bool checkInclusionTwo(string s1, string s2);
    // 3. 无重复字符的最长子串
    int lengthOfLongestSubstring(string s);
    // 209. 长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。输入的为正整数，没哟负数则可以考虑使用滑动窗口
    // 典型的滑动窗口算法
    int minSubArrayLen(int target, vector<int>& nums);
    
    // strstr的实现也可以当作滑动窗口的案例，一个目标作为整体窗口在另外一个目标中滑动
    // 28. 实现 strStr()
    // needlle在分别以haystack的[0,length-needlelength]滑动
    int strStr(string haystack, string needle);
    // 718. 最长重复子数组 可以使用DP方法解答，也可以使用滑动窗口
    // 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 A在B+B在A中滑动得到的结果才是解
    int findLength(vector<int>& A, vector<int>& B);
    int findLengthSlideWindow(vector<int>& A, vector<int>& B);
    int maxLength(vector<int>& A, vector<int>& B, int addA, int addB, int len);
    
    //
    //
    //      排列问题（注意给定的输入重复和非重复的问题，得到排列组合一定是无重复的组合）
    //      BackTrace 回溯算法，N叉树的遍历问题，根据条件进行剪枝操作
    //
    //
    
    // 31. 下一个排列
    // https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
    void nextPermutation(vector<int>& nums);
    // 46. 全排列 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
    
    // 47. 全排列 II 给定一个可以重复 数字的序列，返回其所有可能的全排列。
    
    // 面试题 08.07. 无重复字符串的排列组合
    // 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
    
    
    //
    // N-Sum
    //
    // 1. 两数之和
    // 两种解法：hashtable，不用先排序
    // 左右指针算法，题目描述的为一定有一组，每次只移动一个指针即可,需要先排序 NLogN
    vector<int> twoSum(vector<int>& nums, int target);
    // 15. 三数之和 （排序，去重+two-sum的双指针方法，需要排序为前提）
    vector<vector<int>> threeSum(vector<int>& nums);
    
    
    // 560. 和为K的子数组 prefix-sum解法，不能用滑动窗口因为存在负数
    // 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 prefix-sum
    int subarraySum(vector<int>& nums, int k);
    // 713. 乘积小于K的子数组 输入都是正整数，每次乘法结果都是变大
    int numSubarrayProductLessThanK(vector<int>& nums, int k);
    // 152. 乘积最大子数组，可以不用dp的解法，存在负数，负数会将最大值变成最小值，遇到负数交换下保存的最大值和最小值，根据
    // 当前的nums[i] 和乘积 更新保存的最大值和最小值
    int maxProduct(vector<int>& nums);
    
    // 69. x 的平方根
    int mySqrt(int x);
    
    // 50. Pow(x, n)
    double myPow(double x, int n);
    double myPowRecursion(double x, int n);
    
    // 翻转只比较一半的数字，前提是排除了负数+结尾为0的数字
    // 9. 回文数
    bool isPalindrome(int x);
    // 回文链表
    // 7. 整数反转,假设环境不允许存储 64 位整数（有符号或无符号）,注意溢出的问题
    // 如何判断溢出问题，INT_MIN，INT_MAX
    int reverse(int x);
    
    // 54. 螺旋矩阵
    vector<int> spiralOrder(vector<vector<int>>& matrix);
    // 转置矩阵
    vector<vector<int>> transposedMatrix(vector<vector<int>>& matrix);
    // 394. 字符串解码
    string decodeString(string s);
    // 224. 基本计算器
    // 输入：s = "(1+(4+5+2)-3)+(6+8)"
    // 输出：23
    int calculateHard(string s);
    // 227. 基本计算器 II
    // 输入: "3+2*2"
    // 输出: 7
    int calculateMedium(string s);
};
#endif /* CommonSolution_h */
